package com.xyhuo.leetcode.december;

/**
 * 搜索二维矩阵
 * https://leetcode.cn/problems/search-a-2d-matrix/
 *
 * @time 2023/12/28
 */
public class SearchMatrix {

//    public static void main(String[] args) {
//        SearchMatrix sm = new SearchMatrix();
//        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
//        boolean ans = sm.searchMatrix(matrix, 3);
//        System.out.println(ans);
//    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int start_m = 0, start_n = 0, end_m = matrix.length - 1, end_n = matrix[0].length - 1;

        while (true) {
            int left = start_m * n + start_n;
            int right = end_m * n + end_n;
            if (left > right) {
                break;
            }
            int plus = (right - left) / 2;
            int middle_m = start_m + plus / n;
            int middle_n = start_n + plus % n;
            if (middle_n >= n) {
                middle_m++;
                middle_n = middle_n % n;
            }
            if (target == matrix[middle_m][middle_n]) {
                return true;
            } else if (target < matrix[middle_m][middle_n]) {
                if (middle_n == 0) {
                    end_m = middle_m - 1;
                    end_n = n - 1;
                } else {
                    end_m = middle_m;
                    end_n = middle_n - 1;
                }
            } else {
                if (middle_n == n - 1) {
                    start_m = middle_m + 1;
                    start_n = 0;
                } else {
                    start_m = middle_m;
                    start_n = middle_n + 1;
                }
            }
        }
        return false;
    }
}
